import java.util.*;

import static java.lang.Math.max;

public class BinaryTree {
    //节点结构
    static class TreeNode{
        public char val;
        public TreeNode left;//左孩子引用
        public TreeNode right;//右孩子引用

        public TreeNode(char val){
            this.val=val;
        }
    }
    public TreeNode root;
    //先序序列创建二叉树
    public static int i=0;
    public static TreeNode creatTree(String s){
        TreeNode tree=null;
        if(s.charAt(i)=='#') {
            i++;
        }
        else{
            tree=new TreeNode(s.charAt(i));
            i++;
            tree.left=creatTree(s);
            tree.right=creatTree(s);
        }
        return tree;
    }
    //简单模拟二叉树的结构
    public void createTree(){
        TreeNode A=new TreeNode('A');
        TreeNode B=new TreeNode('B');
        TreeNode C=new TreeNode('C');
        TreeNode D=new TreeNode('D');
        TreeNode E=new TreeNode('E');
        TreeNode F=new TreeNode('F');
        TreeNode G=new TreeNode('G');
        TreeNode H=new TreeNode('H');

        A.left=B;
        A.right=C;
        B.left=D;
        B.right=E;
        C.left=F;
        C.right=G;
        E.right=H;
        root=A;
    }
    // 前序遍历(无返回值类型)(递归遍历思维)
     public void preOrder(TreeNode root){
        if(root==null){
            return;
        }
        System.out.println(root.val+" ");
        preOrder(root.left);
        preOrder(root.right);
     }
     // 有返回值类型(递归遍历思维)
    public List<Character> preorderTraversal1(TreeNode root) {
        List<Character> ret=new ArrayList();
        preorder(root,ret);
        return ret;
    }
    public void preorder(TreeNode root,List<Character> ret){
        if(root==null){
            return;
        }
        ret.add(root.val);
        preorder(root.left,ret);
        preorder(root.right,ret);
    }
    // 有返回值类型(递归子问题思维)
    public List<Character> preorderTraversal2(TreeNode root) {
        List<Character> ret = new ArrayList<>();
        if(root==null){
            return ret;
        }
        ret.add(root.val);
        List<Character> leftTree = new ArrayList<>();
        ret.addAll(leftTree);
        List<Character> rightTree = new ArrayList<>();
        ret.addAll(rightTree);
        return ret;

    }
    //非递归前序遍历
//    public List<Integer> preorderTraversal(TreeNode root) {
//        List<Integer> ret=new ArrayList();
//        preorder(root,ret);
//        return ret;
//    }
//    public void preorder(TreeNode root,List<Integer> ret){
//        if(root==null){
//            return;
//        }
//        Stack<TreeNode> stack=new Stack<>();
//        TreeNode cur=root;
//        while(cur!=null||!stack.isEmpty()){
//            while(cur!=null){
//                stack.push(cur);
//                ret.add(cur.val);
//                cur=cur.left;
//            }
//            cur=stack.pop().right;
//        }
//    }
    // 中序遍历
     public void inOrder(TreeNode root){
         if(root==null){
             return;
         }
         inOrder(root.left);
         System.out.println(root.val+" ");
         inOrder(root.right);
     }
     //非递归中序遍历
//    public List<Integer> inorderTraversal(TreeNode root) {
//        List<Integer> ret=new ArrayList();
//        inorder(root,ret);
//        return ret;
//    }
//    public void inorder(TreeNode root,List<Integer> ret){
//        if(root==null){
//            return;
//        }
//        Stack<TreeNode> stack=new Stack<>();
//        TreeNode cur=root;
//        while(cur!=null||!stack.isEmpty()){
//            while(cur!=null){
//                stack.push(cur);
//                cur=cur.left;
//            }
//            TreeNode top=stack.pop();
//            ret.add(top.val);
//            cur=top.right;
//        }
//    }
    // 后序遍历
     public void postOrde(TreeNode root){
         if(root==null){
             return;
         }
         postOrde(root.left);
         postOrde(root.right);
         System.out.println(root.val+" ");
     }
     //非递归后序遍历
//    public List<Integer> postorderTraversal(TreeNode root) {
//        List<Integer> list=new ArrayList<>();
//        Stack<TreeNode> stack=new Stack<>();
//        TreeNode cur=root;
//        TreeNode prev=null;
//        while(cur!=null||!stack.isEmpty()){
//            while(cur!=null){
//                stack.push(cur);
//                cur=cur.left;
//            }
//            TreeNode top=stack.peek();
//            if(top.right==null||top.right==prev){
//                stack.pop();
//                list.add(top.val);
//                prev=top;
//            }else{
//                cur=top.right;
//            }
//        }
//        return list;
//    }
    // 获取树中节点的个数(遍历思路)
    public static int s=0;
    int size(TreeNode root){
        if(root==null){
            return s;
        }
        s++;
        size(root.left);
        size(root.right);
        return s;
    }
    // 获取树中节点的个数(子问题思路)
    int size2(TreeNode root){
        if(root==null){
            return 0;
        }
        return size2(root.left)+size2(root.right)+1;
    }
    // 获取叶子节点的个数(遍历思路)
    public static int count;
    int getLeafNodeCount(TreeNode root){
        if(root==null) return 0;
        if(root.left==null&&root.right==null){
            count++;
        }
        getLeafNodeCount(root.left);
        getLeafNodeCount(root.right);
        return count;
    }
    // 子问题思路-求叶子结点个数
    int getLeafNodeCount2(TreeNode root){
        if(root==null) return 0;
        if(root.left==null&&root.right==null){
            return 1;
        }
        return getLeafNodeCount2(root.left)+getLeafNodeCount2(root.right);
    }
    // 获取第K层节点的个数
    int getKLevelNodeCount(TreeNode root,int k){
        if(root==null) return 0;
        if(k==1) return 1;
        return getKLevelNodeCount(root.left,k-1)+getKLevelNodeCount(root.right,k-1);
    }
    // 获取二叉树的高度(O(n))
    int getHeight(TreeNode root){
        if(root==null) return 0;
        return max(getHeight(root.left),getHeight(root.right))+1;
    }
    // 检测值为value的元素是否存在
    TreeNode find(TreeNode root, int val){
        if(root==null) return null;
        if(root.val==val) return root;
        TreeNode leftTree=find(root.left,val);
        if(leftTree!=null){
            return leftTree;
        }
        TreeNode rightTree=find(root.right,val);
        if(rightTree!=null){
            return rightTree;
        }
        return null;

    }
    //层序遍历(非递归)(借助队列)
    void levelOrder(TreeNode root){
        if(root==null) return;
        Queue<TreeNode> queue=new LinkedList<>();
        queue.offer(root);
        TreeNode cur=null;
        while(!queue.isEmpty()) {
            cur = queue.poll();
            System.out.print(cur.val + " ");
            if (cur.left != null) {
                queue.offer(cur.left);
            }
            if (cur.right != null) {
                queue.offer(cur.right);
            }
        }
        System.out.println();
    }
    //层序遍历(将每层节点放入一个list2，将所有的list2放入一个list1)
    public List<List<Character>> levelOrder2(TreeNode root) {
        List<List<Character>> list1 = new ArrayList<>();
        if(root==null) return list1;
        Queue<TreeNode> queue=new LinkedList<>();
        queue.offer(root);
        while(!queue.isEmpty()){
            int size=queue.size();
            List<Character> list2=new ArrayList<>();
            //每一层放入一个list2
            while(size!=0){
                TreeNode cur = queue.poll();
                list2.add(cur.val);
                size--;
                if (cur.left != null) {
                    queue.offer(cur.left);
                }
                if (cur.right != null) {
                    queue.offer(cur.right);
                }
            }
            list1.add(list2);
        }
        return list1;
    }

    // 判断一棵树是不是完全二叉树
    boolean isCompleteTree(TreeNode root){
        if(root==null) return false;
        Queue<TreeNode> queue=new LinkedList<>();
        queue.offer(root);
        //按照层序遍历对队列操作
        while(!queue.isEmpty()){
            TreeNode cur=queue.poll();
            if(cur!=null){
                queue.offer(cur.left);
                queue.offer(cur.right);
            }else break;

        }
        //如果队列出队第一个null元素后还有非null元素则说明非完全二叉树
        while(!queue.isEmpty()){
            TreeNode cur1=queue.peek();
            if(cur1==null){
                queue.poll();
            }else return false;
        }
        return true;
    }
    //判断两个树是不是相同的树,时间复杂度O(min(m,n))m,n为两树的节点数
    public boolean isSameTree(TreeNode p, TreeNode q) {
        if(p==null&&q==null) return true;
        if(p==null||q==null) return false;
        if(p.val!=q.val) return false;
        return isSameTree(p.left,q.left)&&isSameTree(p.right,q.right);
    }
    //另一颗树的子树，时间复杂度O(m*n)
    public boolean isSubtree(TreeNode root, TreeNode subRoot) {
        if(root==null) return false;
        return isSameTree(root,subRoot) || isSubtree(root.left,subRoot) || isSubtree(root.right,subRoot);
    }
    //平衡二叉树1(O(n^2))
    public boolean isBalanced1(TreeNode root) {
        if(root==null) return true;
        return Math.abs(getHeight(root.left)-getHeight(root.right))<=1 && isBalanced1(root.left) && isBalanced1(root.right);
    }
    //平衡二叉树2(O(n))
    // 获取二叉树的高度改造版(O(n))
    int Height(TreeNode root){
        if(root==null) return 0;
        int leftH=Height(root.left);
        int rightH=Height(root.right);

        if(leftH>=0&&rightH>=0&&Math.abs(leftH-rightH)<=1){
            return Math.max(leftH,rightH)+1;
        }else{
            return -1;
        }
    }
    public boolean isBalanced2(TreeNode root) {
        if(root==null) return true;
        return Height(root) >= 0?true:false;

    }
    //对称二叉树
    public boolean isSymmetricChild(TreeNode leftTree,TreeNode rightTree) {
        if(leftTree == null && rightTree != null ) return false;
        if(leftTree != null && rightTree == null ) return false;
        if(leftTree == null && rightTree == null ) return true;
        if(leftTree.val!=rightTree.val) return false;
        return isSymmetricChild(leftTree.left,rightTree.right) &&
                isSymmetricChild(leftTree.right,rightTree.left);

    }
    public boolean isSymmetric(TreeNode root) {
        if(root==null) return true;
        return isSymmetricChild(root.left,root.right);
    }
    //LCA问题
    //1.如果是孩子双亲表示法，可以转化为求两个链表交点
    //2.将两个节点的路径节点放入两个栈，节点多的先出差值个节点，然后一起比较出栈，相同的节点就是公共祖先
    //3.p,q有三种情况(1)p或q为根节点，此时p或q为公共祖先(2)p或q在根节点两侧，此时根节点为公共节点(3)p和q
    //在根节点同一侧，此时需要分别递归左侧或者右侧进行查找

    //解法2
    public TreeNode lowestCommonAncestor1(TreeNode root, TreeNode p, TreeNode q) {
        if(root==null) return null;
        if(root==p||root==q) return root;
        //如果根不是，在左树和右树找
        TreeNode leftTree=lowestCommonAncestor1(root.left,p,q);
        TreeNode rightTree=lowestCommonAncestor1(root.right,p,q);
        if(leftTree!=null&&rightTree!=null){
            return root;
        }else if(leftTree!=null){
            return leftTree;
        }else if(rightTree!=null){
            return rightTree;
        }
        return null;
    }

    //解法3
    public boolean getPath(TreeNode root, TreeNode node,Stack<TreeNode> stack){
        if(root==null) return false;
        stack.push(root);
        if(root==node){
            return true;
        }
        boolean leftTree=getPath(root.left,node,stack);
        boolean rightTree=getPath(root.right,node,stack);
        if(leftTree==true||rightTree==true){
            return true;
        }else{
            stack.pop();
            return false;
        }
    }
    public TreeNode lowestCommonAncestor2(TreeNode root, TreeNode p, TreeNode q) {
        Stack<TreeNode> stack1=new Stack<TreeNode>();
        getPath(root,p,stack1);
        Stack<TreeNode> stack2=new Stack<TreeNode>();
        getPath(root,q,stack2);
        int size1=stack1.size();
        int size2=stack2.size();
        int size=size1>size2?(size1-size2):(size2-size1);
        while(size!=0){
            if(size1>size2){
                stack1.pop();
            }else{
                stack2.pop();
            }
            size--;
        }
        TreeNode l=null;
        TreeNode r=null;
        while(!stack1.isEmpty()){
            l=stack1.pop();
            r=stack2.pop();
            if(l==r) break;
        }
        return l;
    }
    //输入一棵二叉搜索树，将该二叉搜索树转换成一个排序的双向链表
    public TreeNode pre=null;
    public void ConvertTree(TreeNode pCur){
        if(pCur==null) return;
        ConvertTree(pCur.left);
        pCur.left=pre;
        if(pre!=null){
            pre.right=pCur;
        }
        pre=pCur;
        ConvertTree(pCur.right);
    }
    public TreeNode Convert(TreeNode pRootOfTree) {
        if(pRootOfTree==null) return null;
        ConvertTree(pRootOfTree);
        TreeNode head=pRootOfTree;
        while(head.left!=null){
            head=head.left;
        }
        return head;
    }
    // 根据一棵树的前序遍历与中序遍历构造二叉树
//    public int preIndex=0;
//    public TreeNode buildChildTree(int[] preorder, int[] inorder,int inbegin,int inend){
//        if(inbegin>inend) return null;
//        TreeNode root=new TreeNode(preorder[preIndex]);
//        int rootIndex=findIndex(inorder,inbegin,inend,preorder[preIndex]);
//        preIndex++;
//        root.left=buildChildTree(preorder,inorder,inbegin,rootIndex-1);
//        root.right=buildChildTree(preorder,inorder,rootIndex+1,inend);
//        return root;
//    }
//    public int findIndex(int[] inorder,int inbegin,int inend,int val){
//        for(int i =inbegin;i<=inend;i++){
//            if(inorder[i]==val){
//                return i;
//            }
//        }
//        return -1;
//    }
//    public TreeNode buildTree(int[] preorder, int[] inorder) {
//        return buildChildTree(preorder,inorder,0,inorder.length-1);
//    }
    //二叉树转化为括号字符串
    public void tree2strChild(TreeNode root,StringBuilder str) {
        if(root==null) return;
        str.append(root.val);
        if(root.left!=null){
            str.append("(");
            tree2strChild(root.left,str);
            str.append(")");
        }else{
            if(root.right==null){
                return;
            }else{
                str.append("()");
            }
        }
        if(root.right==null){
            return;
        }else{
            str.append("(");
            tree2strChild(root.right,str);
            str.append(")");
        }
    }
    public String tree2str(TreeNode root) {
        if(root==null){
            return null;
        }
        StringBuilder str=new StringBuilder();
        tree2strChild(root,str);
        return str.toString();
    }

}
